import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>(); // 用于存储最终结果
        if (root == null) {
            return levelOrder; // 如果根节点为空，直接返回空结果
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>(); // 创建一个队列用于层次遍历
        queue.offer(root); // 将根节点加入队列
        while (!queue.isEmpty()) { // 当队列不为空时，继续遍历
            List<Integer> level = new ArrayList<Integer>(); // 用于存储当前层的节点值
            int size = queue.size(); // 当前层的节点数量
            for (int i = 0; i < size; i++) { // 遍历当前层的所有节点
                TreeNode node = queue.poll(); // 从队列中取出一个节点
                level.add(node.val); // 将节点的值加入当前层的列表
                TreeNode left = node.left, right = node.right; // 获取左右子节点
                if (left != null) {
                    queue.offer(left); // 如果左子节点不为空，加入队列
                }
                if (right != null) {
                    queue.offer(right); // 如果右子节点不为空，加入队列
                }
            }
            levelOrder.add(0, level); // 将当前层的结果插入到结果列表的最前面
        }
        return levelOrder; // 返回最终结果
    }

    public static void main(String[] args) {
        // 创建测试用的二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        // 调用方法并打印结果
        Solution solution = new Solution();
        List<List<Integer>> result = solution.levelOrderBottom(root);
        for (List<Integer> level : result) {
            System.out.println(level);
        }
    }
}

// TreeNode 类的定义
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}